package com.gitee.swsk33.algorithms.tree.huffmancode;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 赫夫曼编码树
 */
public class HuffmanTreeCode {

	/**
	 * 赫夫曼树根结点
	 */
	private TreeNode root;

	/**
	 * 该赫夫曼树的所有叶子结点，用于解码时进行索引
	 */
	private TreeNode[] leaves;

	/**
	 * 构造一个赫夫曼树
	 *
	 * @param nodes 传入结点集合
	 */
	public HuffmanTreeCode(List<TreeNode> nodes) {
		// 先把结点列表复制为一数组赋值给叶子结点数组属性（数组中存放的是引用而非结点的深复制）
		leaves = nodes.toArray(new TreeNode[0]);
		while (nodes.size() > 1) {
			// 权重最小结点
			TreeNode minimum = nodes.get(0);
			// 先找出最小结点
			for (int i = 1; i < nodes.size(); i++) {
				if (nodes.get(i).getWeight() < minimum.getWeight()) {
					minimum = nodes.get(i);
				}
			}
			// 从列表中移除最小节点
			nodes.remove(minimum);
			// 再找权重倒数第二小的结点
			TreeNode penultimate = nodes.get(0);
			for (int i = 1; i < nodes.size(); i++) {
				if (nodes.get(i).getWeight() < penultimate.getWeight()) {
					penultimate = nodes.get(i);
				}
			}
			// 移除倒二结点
			nodes.remove(penultimate);
			// 把两者作为左右孩子构成一个二叉树
			TreeNode newTreeRoot = new TreeNode();
			// 小的在左大的在右
			newTreeRoot.setLeft(minimum);
			newTreeRoot.setRight(penultimate);
			newTreeRoot.setWeight(minimum.getWeight() + penultimate.getWeight());
			// 记得还要设定两者的双亲结点
			minimum.setParent(newTreeRoot);
			penultimate.setParent(newTreeRoot);
			// 然后把这个新的二叉树节点加入结点集合
			nodes.add(newTreeRoot);
		}
		// 最后，集合中只有一个结点就是该赫夫曼树的根节点
		root = nodes.get(0);
	}

	/**
	 * 获取该赫夫曼树的所有字母的编码
	 *
	 * @return 所有字母对编码的映射表
	 */
	public Map<Character, String> getAllCharCode() {
		Map<Character, String> result = new HashMap<>();
		// 遍历叶子结点逆向往上求编码
		for (TreeNode node : leaves) {
			String code = "";
			// 一直往上直到双亲结点为null时，说明到了根节点
			for (TreeNode current = node; current.getParent() != null; current = current.getParent()) {
				// 判断当前结点是其双亲结点的左孩子还是右孩子
				if (current == current.getParent().getLeft()) {
					// 由于是逆向编码，我们要按照和正常读的时候相反着来
					code = 0 + code;
				} else {
					code = 1 + code;
				}
			}
			// 记录到结果表
			result.put(node.getData(), code);
		}
		return result;
	}

}